import random
import matplotlib.pyplot as plt
import math
import time


"""每次生成一个图后截屏然后叉掉，等待一段时间后就会生成下一个算法的结果图，最终将时间统计起来，到excel画出时间对比图"""




"""数据生成函数，生成size大小的数据量"""
def generate_data(size, x_axis, y_axis):
    data = []
    for i in range(size):
        x = random.uniform(x_axis.min, x_axis.max)
        y = random.uniform(y_axis.min, y_axis.max)
        p = Point(x, y)
        data.append(p)
    return data

"""点类"""
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.angle = 0
        
"""坐标轴类，只是规定坐标轴范围"""
class Axis:
    def __init__(self, min, max):
        self.min = min
        self.max = max

"""数据生成函数，生成size大小的数据量"""
def judge(a, b, c):
    ans = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x)
    if ans >= 0:
        return True
    else:
        return False

"""求叉积，用于判断是否满足凸包全左转的条件"""
def cross_product(A, B, P):
    ans = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x)
    return ans

"""已知3点，判断第四点是否存在于3点围成的三角形中，如果是则第四点不是凸包集的点"""
"""核心在于判断P点是否在三条边向量（AB/BC/CA）的同侧"""
def istriangle(a, b, c, p):
    signOfTrig = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
    signOfAB = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)
    signOfCA = (a.x - c.x) * (p.y - c.y) - (a.y - c.y) * (p.x - c.x)
    signOfBC = (c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x)

    d1 = (signOfAB * signOfTrig > 0)
    d2 = (signOfCA * signOfTrig > 0)
    d3 = (signOfBC * signOfTrig > 0)

    return d1 and d2 and d3

"""------------------------------------------枚举法---------------------------------------------------"""
def enumeration_method(size, data, data_o, show=True):
    start_time = time.time()
    L = []
    R = []
    flag = [0 for x in range(size)]

    for i in range(size - 3):
        if flag[i] == 1:
            continue
        for j in range(i + 1, size - 2):
            if flag[j] == 1:
                continue
            for k in range(j + 1, size - 1):
                if flag[k] == 1:
                    continue
                for l in range(k + 1, size):
                    if flag[l] == 1:
                        continue
                    elif istriangle(data_o[i], data_o[j], data_o[k], data_o[l]):
                        flag[l] = 1
                        continue
                    elif istriangle(data_o[l], data_o[j], data_o[k], data_o[i]):
                        flag[i] = 1
                        continue
                    elif istriangle(data_o[i], data_o[l], data_o[k], data_o[j]):
                        flag[j] = 1
                        continue
                    elif istriangle(data_o[i], data_o[j], data_o[l], data_o[k]):
                        flag[k] = 1
    for i in range(size):
        if flag[i] == 0:
            data.append(data_o[i])
    data = sorted(data, key=lambda point: (point.x, point.y))

    A = data[0]
    B = data[-1]
    del data[0]
    del data[-1]
    for P in data:
        if cross_product(A, B, P) > 0:
            L.append(P)
        elif cross_product(A, B, P) < 0:
            R.append(P)
    Lr = L.reverse()
    end_time = time.time()
    print("enumeration method cost {:.1f}ms".format((end_time - start_time) * 1000)) # 图中的信息如果用中文输出的话可能会乱码，可能是个人电脑原因

    if show:
        for p in data_o:
            plt.scatter(p.x, p.y, c='b', marker='.')

        plt.scatter(A.x, A.y, c='r', marker='.')
        plt.plot([A.x, R[0].x], [A.y, R[0].y], color='r')
        for i in range(len(R) - 1):
            plt.scatter(R[i].x, R[i].y, c='r', marker='.')
            plt.plot([R[i].x, R[i + 1].x], [R[i].y, R[i + 1].y], color='r')
        plt.scatter(R[-1].x, R[-1].y, c='r', marker='.')
        plt.plot([R[-1].x, B.x], [R[-1].y, B.y], color='r')
        plt.scatter(B.x, B.y, c='r', marker='.')
        plt.plot([B.x, L[0].x], [B.y, L[0].y], color='r')
        for i in range(len(L) - 1):
            plt.scatter(L[i].x, L[i].y, c='r', marker='.')
            plt.plot([L[i].x, L[i + 1].x], [L[i].y, L[i + 1].y], color='r')
        plt.scatter(L[-1].x, L[-1].y, c='r', marker='.')
        plt.plot([L[-1].x, A.x], [L[-1].y, A.y], color='r')
        plt.title('enumeration')
        #plt.savefig("{}_size=2000.png".format(enumeration_method.__name__))# 用于保存图片
        plt.show()

"""------------------------------------------GrahamScanCH算法---------------------------------------------------"""
def GrahamScan_method(data, show=True):
    start_time = time.time()
    p0 = Point(101, 101)
    for p in data:  # 找到最左侧的点
        if p.y < p0.y:
            p0 = p
        elif p.y == p0.y and p.x < p0.x:
            p0 = p
    data.remove(p0)
    for p in data:  # 求其他点与最左侧点的极角
        if p.x == p0.x:
            p.angle = math.pi / 2
        elif p.x > p0.x:
            p.angle = math.atan((p.y - p0.y) / (p.x - p0.x))
        else:
            p.angle = math.atan((p0.x - p.x) / (p.y - p0.y)) + math.pi / 2
    data = sorted(data, key=lambda point: point.angle)  # 按极角对点进行排序
    stack = [p0, data[0], data[1]]
    for i in range(2, len(data)):  # 由近及远的对每组3个点进行判断，看是否满足凸包条件
        while judge(stack[-2], stack[-1], data[i]):
            stack.pop(-1)
        stack.append(data[i])
    end_time = time.time()
    print("Graham-Scan method cost {:.1f}ms".format((end_time - start_time) * 1000))

    if show:
        plt.scatter(p0.x, p0.y, c='b', marker='.')
        for p in data:
            plt.scatter(p.x, p.y, c='b', marker='.')
        for i in range(len(stack) - 1):
            plt.scatter(stack[i].x, stack[i].y, c='r', marker='.')
            plt.plot([stack[i].x, stack[i + 1].x], [stack[i].y, stack[i + 1].y], color='r')
        plt.scatter(stack[-1].x, stack[-1].y, c='r', marker='.')
        plt.plot([stack[-1].x, p0.x], [stack[-1].y, p0.y], color='r')
        plt.title('Graham-Scan')
        #plt.savefig("{}_size=2000.png".format(GrahamScan_method.__name__))# 用于保存图片
        plt.show()



"""------------------------------------------分治法---------------------------------------------------"""
"""划分区域的函数"""
def divide(data):
    maxn = -1
    minn = 101
    data1 = []
    data2 = []
    for p in data:
        if p.x < minn:
            minn = p.x
        if p.x > maxn:
            maxn = p.x
    minddle = (maxn + minn) / 2  # 通过找到最大最小值点，来找到中心分割位置
    for p in data:
        if p.x <= minddle:
            data1.append(p)
        else:
            data2.append(p)
    return data1, data2


def conquer(data1, data2):
    if len(data1) == 0:
        return data2
    if len(data2) == 0:
        return data1
    # 求纵坐标最小的点
    if data1[0].y <= data2[0].y:
        p0 = data1[0]
        data1.remove(p0)
        flag = 1
    else:
        p0 = data2[0]
        data2.remove(p0)
        flag = 0
    # 计算每一个点相对于p0的极角
    p0.angle = 0
    for p in data1:
        if p.x == p0.x:
            p.angle = math.pi / 2
        elif p.x > p0.x:
            p.angle = math.atan((p.y - p0.y) / (p.x - p0.x))
        else:
            p.angle = math.atan((p0.x - p.x) / (p.y - p0.y)) + math.pi / 2
    for p in data2:
        if p.x == p0.x:
            p.angle = math.pi / 2
        elif p.x > p0.x:
            p.angle = math.atan((p.y - p0.y) / (p.x - p0.x))
        else:
            p.angle = math.atan((p0.x - p.x) / (p.y - p0.y)) + math.pi / 2
    # 利用data1和data2逆时针排序的特点，在线性时间内将所有点按极角大小排好序
    min1 = 10
    max1 = -1
    min2 = 10
    max2 = -1
    if flag == 0:
        minindex = -1
        maxindex = -1
        for i in range(len(data1)):
            if data1[i].angle > max1:
                max1 = data1[i].angle
                maxindex = i
            if data1[i].angle < min1:
                min1 = data1[i].angle
                minindex = i
        if minindex <= maxindex:
            data3 = data1[minindex:maxindex + 1]
            data4 = []
            if minindex != 0:
                data4 = data4 + data1[minindex - 1::-1]
            if maxindex != len(data1) - 1:
                data4 = data4 + data1[-1:maxindex:-1]
        else:
            data3 = data1[minindex:maxindex:-1]
            data4 = []
            data4 = data4 + data1[minindex + 1:]
            data4 = data4 + data1[0:maxindex + 1]
        data5 = []
        i = 0
        j = 0
        while i < len(data3) and j < len(data4):
            if data3[i].angle <= data4[j].angle:
                data5.append(data3[i])
                i = i + 1
            else:
                data5.append(data4[j])
                j = j + 1
        while i < len(data3):
            data5.append(data3[i])
            i = i + 1
        while j < len(data4):
            data5.append(data4[j])
            j = j + 1
        data6 = []
        i = 0
        j = 0
        while i < len(data2) and j < len(data5):
            if data2[i].angle <= data5[j].angle:
                data6.append(data2[i])
                i = i + 1
            else:
                data6.append(data5[j])
                j = j + 1
        while i < len(data2):
            data6.append(data2[i])
            i = i + 1
        while j < len(data5):
            data6.append(data5[j])
            j = j + 1
    else:
        maxindex = -1
        minindex = -1
        for i in range(len(data2)):
            if data2[i].angle > max2:
                max2 = data2[i].angle
                maxindex = i
            if data2[i].angle < min2:
                min2 = data2[i].angle
                minindex = i
        if minindex <= maxindex:
            data3 = data2[minindex:maxindex + 1]
            data4 = []
            if minindex != 0:
                data4 = data4 + data2[minindex - 1::-1]
            if maxindex != len(data2) - 1:
                data4 = data4 + data2[-1:maxindex:-1]
        else:
            data3 = data2[minindex:maxindex:-1]
            data4 = []
            data4 = data4 + data2[minindex + 1:]
            data4 = data4 + data2[0:maxindex + 1]
        data5 = []

        i = 0
        j = 0
        while i < len(data3) and j < len(data4):
            if data3[i].angle <= data4[j].angle:
                data5.append(data3[i])
                i = i + 1
            else:
                data5.append(data4[j])
                j = j + 1
        while i < len(data3):
            data5.append(data3[i])
            i = i + 1
        while j < len(data4):
            data5.append(data4[j])
            j = j + 1
        data6 = []
        i = 0
        j = 0
        while i < len(data1) and j < len(data5):
            if data1[i].angle <= data5[j].angle:
                data6.append(data1[i])
                i = i + 1
            else:
                data6.append(data5[j])
                j = j + 1
        while i < len(data1):
            data6.append(data1[i])
            i = i + 1
        while j < len(data5):
            data6.append(data5[j])
            j = j + 1
    if len(data6) <= 1:
        return [p0] + data6
    stack = [p0, data6[0], data6[1]]
    if len(data6) == 2:
        return stack
    for i in range(2, len(data6)):
        while judge(stack[-2], stack[-1], data6[i]):
            stack.pop(-1)
        stack.append(data6[i])
    return stack

def divide_and_conquer(data):
    if len(data) <= 1:
        return data
    if len(data) == 2:
        return sorted(data, key=lambda point: (point.y, point.x))
    elif len(data) == 3:
        p0 = Point(101, 101)
        for p in data:
            if p.y < p0.y:
                p0 = p
            elif p.y == p0.y and p.x < p0.x:
                p0 = p
        data.remove(p0)
        for p in data:
            if p.x == p0.x:
                p.angle = math.pi / 2
            elif p.x > p0.x:
                p.angle = math.atan((p.y - p0.y) / (p.x - p0.x))
            else:
                p.angle = math.atan((p0.x - p.x) / (p.y - p0.y)) + math.pi / 2
        res = [p0]
        if data[0].angle <= data[1].angle:
            res.append(data[0])
            res.append(data[1])
        else:
            res.append(data[1])
            res.append(data[0])
        return res
    data1, data2 = divide(data)
    data1 = divide_and_conquer(data1)
    data2 = divide_and_conquer(data2)
    data = conquer(data1, data2)
    return data

"""分治法主函数"""
def Divide_method(data, show=True):
    start_time = time.time()
    stack = divide_and_conquer(data)
    end_time = time.time()
    print("divide and conquer method cost {:.1f}ms".format((end_time - start_time) * 1000))

    if show:
        for p in data:
            plt.scatter(p.x, p.y, c='b', marker='.')
        for i in range(len(stack) - 1):
            plt.scatter(stack[i].x, stack[i].y, c='r', marker='.')
            plt.plot([stack[i].x, stack[i + 1].x], [stack[i].y, stack[i + 1].y], color='r')
        plt.scatter(stack[-1].x, stack[-1].y, c='r', marker='.')
        plt.plot([stack[-1].x, stack[0].x], [stack[-1].y, stack[0].y], color='r')
        plt.title('divide & conquer')
        #plt.savefig("{}_size=2000.png".format(Divide_method.__name__))# 用于保存图片
        plt.show()


def comparation_draw():
    #分别设置size=1000、2000、3000，跑3次实验自己记录3个算法时间，一共9个数据
    sizes = [1000,2000,3000]
    time1 = [368 ,786.9,1547.9]
    time2 = [3,9,11.5]
    time3 = [26,30,37.9]
    plt.plot(sizes,time1,'-o',label = 'enumeration_method')
    plt.plot(sizes,time2,'-o',label = 'GrahamScan_method')
    plt.plot(sizes,time3,'-o',label = 'Divide_method')
    plt.legend()
    for i in range(3):
        plt.text(sizes[i],time1[i]+1 , time1[i])
        plt.text(sizes[i],time2[i]-50 , time2[i])
        plt.text(sizes[i],time3[i]+50 , time3[i])
    plt.title('cost_comparation')
    plt.xlabel("Data Size")
    plt.ylabel("Time (ms)")
    plt.savefig("Time_cost_comparation.png")# 用于保存图片
    plt.show()

# comparation_draw()

x_axis = Axis(0, 100) #限制坐标轴
y_axis = Axis(0, 100)
size = 2000  #按要求改成2000、3000
data = generate_data(size, x_axis, y_axis) #生成0~100范围内的size个随机数
data_o = []
enumeration_method(size, data_o, data) #执行三种算法并画图
GrahamScan_method(data)
Divide_method(data)

